package com.test.leetcode;

import java.util.HashMap;
import java.util.Map;
import java.util.Objects;

/**
 * @author sujiafa
 * @date 2025/3/31
 */
public class n873_最长的斐波那契子序列长度 {

    public int lenLongestFibSubseq(int[] arr) {

        int n = arr.length;
        // 创建一个二维数组dp，dp[i][j]表示以arr[i]和arr[j]结尾的斐波那契子序列的长度
        int[][] dp = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                // 因为斐波那契子序列至少有三个元素，所以初始值设为2
                dp[i][j] = 2;
            }
        }
        // 使用哈希表存储数组中每个元素的索引
        Map<Integer, Integer> numToIndexMap = new HashMap<>();
        for (int i = 0; i < n; i++) {
            numToIndexMap.put(arr[i], i);
        }
        int maxLength = 0;
        for (int j = 1; j < n; j++) {
            for (int i = 0; i < j; i++) {
                Integer k = numToIndexMap.get(arr[i] + arr[j]);
                // 如果sum在数组中存在，且其索引大于j
                if (Objects.nonNull(k) && k > j) {
                    // 更新以arr[j]和arr[k]结尾的斐波那契子序列的长度
                    dp[j][k] = Math.max(dp[j][k], dp[i][j] + 1);
                    maxLength = Math.max(maxLength, dp[j][k]);
                }
            }
        }

        if (maxLength >= 3) {
            return maxLength;
        } else {
            return 0;
        }
    }
}
